import numpy as np
import timeit

np.random.seed(1)


def binary_insert_sort(src):
    for j in range(len(src)):  # 从牌桌上依次抽取牌
        key = src[j]
        left, right = -1, j
        medium = (left + right) // 2
        while left != medium and right != medium:  # 二分搜索查找插入位置medium
            if src[medium] > key:
                right = medium
            else:
                left = medium
            medium = (left + right) // 2
        src[j:j + 1] = src[medium + 1:j]
        src[medium + 1:j] = (key,)
    return src


def insert_sort(src):
    for j in range(1, len(src)):  # 取出第2个到最后一个元素
        key = src[j]
        i = j - 1
        while i >= 0 and src[i] > key:
            src[i + 1] = src[i]
            i -= 1
        src[i + 1] = key
    return src


if __name__ == '__main__':
    ls = list(np.random.randint(-5327, 8765, size=(100,)))
    print(ls)
    binary_insert_sort_time = timeit.Timer("binary_insert_sort(ls)",
                                           "from __main__ import binary_insert_sort,ls")
    print(binary_insert_sort(ls))
    print("二分插入排序时间:{}".format(binary_insert_sort_time.timeit(100)))
    insert_sort_time = timeit.Timer("insert_sort(ls)",
                                    "from __main__ import insert_sort,ls")
    print(insert_sort(ls))
    print("插入排序时间:{}".format(insert_sort_time.timeit(100)))
